package SortMethod;

import SortHelper.SortHelper;

public class PartitionTry {

    //实现并测试快速排序中的一个问题
    //也就是如何得到一个数组，返回一个数并且这个数的左边都比它小，右边都比它大
    public static int partition(Integer[] arr,int l,int r){
        int p = arr[l];
        while (l <= r) {
            if (p == arr[l]){
                if (p > arr[r]){
                    SortHelper.swap(arr,l,r);
                    r--;
                    p = arr[r];
                } else {
                    r--;
                    p = arr[l];
                }
            } else if (p == arr[r]){
                if (p < arr[l]){
                    SortHelper.swap(arr,l,r);
                    l++;
                    p = arr[l];
                } else {
                    l++;
                    p = arr[r];
                }
            }
        }
        return l;
    }

    public static void sort(Integer[] arr,int l,int r){
        if (l > r)return;
        //整体一分为二
        int p = partition(arr,l,r);
        //左边的数来一次
        sort(arr,l,p);
        //右边的数来一次
        sort(arr,p+1,r);
    }

    public static void main(String[] args) {
        Integer[] arr = {6, 1, 3, -4, 2, 5};
        int p = partition(arr,0,arr.length-1);
        System.out.println(p);
        System.out.println(arr[p]);
//        sort(arr,0,arr.length-1);
        for (int n:arr){
            System.out.printf("%d ",n);
        }
    }
}
